#ifndef JUGHEAD_TWOSTACKS_INCLUDED
#define JUGHEAD_TWOSTACKS_INCLUDED
#include <cstdlib>
#include <string>
using namespace std;

class TwoStacks
{
	public:
		int *fst, *sec;
		int *fstmin, *secmin;
		int INF;
		int len1, len2;
		int size;
		TwoStacks();
		void init(int size);
		void push(const int &element);
		void update();
		void destroy();
		void pop();
		int getMinimum();
};
TwoStacks  :: TwoStacks()
{
	fst = sec = fstmin = secmin = NULL;
	len1 = len2 = size = 0;
}
void TwoStacks  :: destroy()
{
	if (fst)
		delete fst;
	if (sec)
		delete sec;
	if (fstmin)
		delete fstmin;
	if (secmin)
		delete secmin;
	fst = sec = fstmin = secmin = NULL;
	len1 = len2 = size = 0;
}

void TwoStacks  :: init(int sz)
{
	destroy();
	size = sz;
	fst = new int[sz + 1];
	sec = new int[sz + 1];
	fstmin = new int[sz + 1];
	secmin = new int[sz + 1];
	len1 = 0;
	len2 = 0;
}

void TwoStacks  :: update()
{
	if (len2 < size) return;
	int mn = sec[len2 - 1];
	int x = 0;
	for (int i = len2 - 1; i >= 0; i--)
	{
		sec[i] += x;
		mn = min(mn, sec[i]);
		fst[len1] = sec[i];
		fstmin[len1++] = mn;
		len2--;
		x++;
	}
}

void TwoStacks  :: push(const int &e)
{
	update();
	sec[len2] = e;
	secmin[len2] = e;
	if (len2 > 0) secmin[len2] = min(secmin[len2 - 1] + 1, e);
	len2++;
	if (len1 + len2 > size) pop();
}

void TwoStacks  :: pop()
{
	len1--;
	update();
}

int TwoStacks  :: getMinimum()
{
	update();
	if (len1 + len2 > size) pop();
	if (len1 && len2)
		return min(fstmin[len1 - 1] + size - len1, secmin[len2 - 1]);
	else if (len1)
		return fstmin[len1 - 1];
	else if (len2)
		return secmin[len2 - 1];
	else return INF;
}

#endif